package sort;

/**
 * 快速排序
 *
 * 思想： 挖坑 + 分治
 */
public class quickSort {
    public static void quickSort(int a[], int begin, int end){
        if(begin < end){
            int x = a[begin];
            int i = begin;
            int j = end;
            while (i < j){
                while(i < j && x < a[j]) {
                    j--;
                }
                if(i < j) {
                    a[i++] = a[j];
                }
                while(i < j && a[i] < x) {
                    i++;
                }
                if(i < j) {
                    a[j--] = a[i];
                }
            }
            a[i] = x;
//            for(int n : a){
//                System.out.print(n + " ");
//            }
//            System.out.println();
            quickSort(a,begin,i - 1);
            quickSort(a,i + 1,end);
        }
    }
}
